package leetcode.hard;

import java.util.Arrays;

public class $72_MinDistance {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] memo = new int[m][n];
        for (int i = 0;i < m;i++) {
            Arrays.fill(memo[i], -1);
        }
        return dp(word1, m - 1, word2, n - 1, memo);
    }

    public int dp(String s1, int i, String s2, int j, int[][] memo) {
        if (i == -1) {
            return j + 1;
        }
        if (j == -1) {
            return i + 1;
        }
        if (memo[i][j] != -1) return memo[i][j];
        if (s1.charAt(i) == s2.charAt(j)) {
            memo[i][j] = dp(s1, i - 1, s2, j - 1, memo);
        } else {
            memo[i][j] = min(dp(s1, i - 1, s2, j, memo) + 1, dp(s1, i, s2, j - 1, memo) + 1, dp(s1, i - 1, s2, j - 1, memo) + 1);
        }

        return memo[i][j];
    }

    public int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}
